1. Field of the Invention
The present invention relates to the field of digital multipliers and more specifically to the addition of partial products.
2. Prior Art
The heart of any computer or microprocessor system is the processor itself. One primary function of any processor is its ability to perform arithmetic or logic operations on various inputs to the processor. Various schemes are known in the prior art to provide arithmetic and logic operations in the arithmetic-logic unit (ALU) of a processor. One necessary function inherent in most processors is the ability to multiply two numbers. The numerical operation of multiplying a multiplicand by a multiplier to derive a product of the two numbers is well-known in the prior art.
Increasing the speed of the multiplier is especially important when the multiplier is on the same integrated circuit as the processor, because the time needed to perform the multiply, rather than the inter-chip communication time, is the dominant delay. Any reduction in the computation time of multiplying two numbers significantly improves the speed of the processor.
Various schemes have been devised to derive the product of two numbers. One of the faster prior art schemes for calculating a product of two numbers uses a Wallace Tree. However, because the pure form of a Wallace Tree is difficult to implement in a semiconductor device, variation to the Wallace Tree were derived to achieve a more regular layout for designing of semiconductor devices. These Wallace Tree variations provide a more regular layout which lends itself to the design of integrated circuits, but at times may be slower in performance to the pure Wallace Tree technique. Trade-offs exist between speed of operation and difficulty of device construction. The prior art references cited below describe some of the prior art techniques for implementing a multiplication scheme which is conducive to the design of numerical processors.
A typical multiplication operation as currently implemented in numerical processors can be divided into three steps. The first step involves the generation of all of the partial products at substantially the same time. The second step involves reducing the partial products to two numbers which have the same sum as the sum of the partial products. Finally in the third step, the two numbers from the second step are added to derive the product. Any improvement in the speed of performing any of the above described three steps will necessarily result in the improved speed of the total multiplication operation. The present invention provides for a faster adder cell which is used in performing the above-described step to reduce the partial products to two numbers.